/*
 * @lc app=leetcode.cn id=22 lang=rust
 *
 * [22] 括号生成
 *
 * https://leetcode.cn/problems/generate-parentheses/description/
 *
 * algorithms
 * Medium (77.59%)
 * Likes:    3602
 * Dislikes: 0
 * Total Accepted:    856.4K
 * Total Submissions: 1.1M
 * Testcase Example:  '3'
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 *
 * 示例 2：
 *
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= n <= 8
 *
 *
 */

// @lc code=start
impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut res = vec![];
        Solution::backtrack(n, n, "".to_string(), &mut res);
        res
    }

    fn backtrack(left: i32, right: i32, s: String, res: &mut Vec<String>) {
        if (left == 0 && right == 0) {
            if Solution::is_valid(&s) {
                res.push(s);
                return;
            }
        }

        if (left < 0 || right < 0) {
            return;
        }

        if (left > 0) {
            Solution::backtrack(left - 1, right, s.clone() + "(", res);
        }

        if (right > 0) {
            Solution::backtrack(left, right - 1, s.clone() + ")", res);
        }
    }

    fn is_valid(s: &str) -> bool {
        let mut stack = vec![];
        for c in s.chars() {
            if c == '(' {
                stack.push(c);
            } else if c == ')' {
                if let Some(_) = stack.pop() {
                    continue;
                } else {
                    return false;
                }
            }
        }

        stack.is_empty()
    }
}
// @lc code=end
